package com.arron.algorithm.leetcodetop100.链表;

import com.arron.algorithm.leetcodetop100.ListNode;
import com.arron.jvm.ref.StrongRefDemo;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 *
 *  141. 环形链表
 *   @see  环形链表I和II#hasCycle2(com.arron.algorithm.leetcodetop100.ListNode)
 *   142. 环形链表 II
 *   @see com.arron.algorithm.leetcodetop100.链表.环形链表I和II#detectCycle(com.arron.algorithm.leetcodetop100.ListNode)
 *
 */
public class 环形链表I和II {


    /**
     * 解法1：使用hash表判断 ，但是会使用额外空间
     * @param head
     * @return
     */
    public boolean hasCycle1(ListNode head) {

        if (head == null) return false;
        Set<ListNode> set = new HashSet<>();
        ListNode p = head;
        while (p.next != null){
            if(set.contains(p)){
                break;
            }
            set.add(p);
            p = p.next;
        }

        if (set.contains(p)){
            return true;
        }
        return false;
    }


    /**
     * 解法2 ：使用双指针法 ，
     *  一个快指针和一个慢指针在一个环中始终会相遇
     * @param head
     * @return
     */
    public boolean hasCycle2(ListNode head) {

        if (head == null || head.next == null) return false;

        ListNode slowNode = head;
        ListNode fastNode = head;

        while (fastNode.next != null && fastNode.next.next !=null){
            slowNode = slowNode.next;
            fastNode = fastNode.next.next;
            if (slowNode == fastNode){
                return true;
            }
        }

        return false;
    }


    /**
     * 环形链表II
     * 找到成环的第一个节点
     *
     */
    public ListNode detectCycle(ListNode head) {

        if (head == null ) return null;

        ListNode slowNode = head;
        ListNode fastNode = head;


        boolean hasCycle = false;
        while (fastNode.next != null && fastNode.next.next !=null){
            slowNode = slowNode.next;
            fastNode = fastNode.next.next;
            if (slowNode == fastNode){
                hasCycle = true;
                break;
            }
        }

        if (hasCycle){
            //如果有环
            slowNode = head;
            while(slowNode!= fastNode){
                slowNode = slowNode.next;
                fastNode = fastNode.next;
            }
            return slowNode;
        }
        return null;
    }


}
